package com.future.offer;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Description: ��ָ Offer II 082. �����ظ�Ԫ�ؼ��ϵ����
 * ����һ���������ظ����ֵ���������?candidates?��һ��Ŀ����?target?���ҳ�?candidates?�����п���ʹ���ֺ�Ϊ?target?����ϡ�
 * <p>
 * candidates?�е�ÿ��������ÿ�������ֻ��ʹ��һ�Σ��⼯���ܰ����ظ�����ϡ�?
 * <p>
 * ?
 * <p>
 * ʾ��?1:
 * <p>
 * ����: candidates =?[10,1,2,7,6,1,5], target =?8,
 * ���:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/4sjJUc
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/12 16:40
 */
public class Solution_82 {

    public static void main(String[] args) {
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        System.out.println(combinationSum2(candidates, target));
        System.out.println();
    }

    /**
     * ����
     *
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Set<List<Integer>> ans1 = new HashSet<>();
        if (candidates == null || candidates.length == 0) {
            return ans;
        }
        process(candidates, 0, target, ans1, new ArrayList<>());
        for (List<Integer> s : ans1) {
            ans.add(s);
        }
        return ans;
    }

    private static void process(int[] candidates, int index, int rest, Set<List<Integer>> ans, List<Integer> tmp) {
        if (rest < 0) {
            return;// �������ᳬʱ������
        }
        if (index == candidates.length) {
            if (rest == 0) {
                List<Integer> al = new ArrayList<Integer>() {{
                    addAll(tmp);
                }};
                // ���򣬾�ȥ��
                al.sort(Comparator.comparingInt(o -> o));
                ans.add(al);
            }
            return;
        }
        // ��ѡ��
        process(candidates, index + 1, rest, ans, tmp);
        // ѡ��
        tmp.add(candidates[index]);
        process(candidates, index + 1, rest - candidates[index], ans, tmp);
        tmp.remove(tmp.size() - 1);
    }

}
